In present day systems large amounts of data may need to be transformed, e.g. from time to frequency domains, etc. For example, in current and planned communication systems data may be transformed using Fast Fourier transforms (FFT) and the inverse (IFFT), which are efficient approaches to evaluating or finding a discrete Fourier transform (DFT) and its inverse. As is known typical FFT algorithms find an N point DFT by factoring N into factors, e.g., n1, n2, . . . , where the product of these factors equals N and then finding, respective and smaller, n1, n2, . . . point DFTs. A factor is often referred to as a radix and thus in this example, the N point DFT can be provided by performing radix n1, radix n2, and radix etc. DFTs.
When an FFT is performed, the resultant transformed data or DFT will not be in order, i.e., for an input vector with N properly ordered elements or data, 0, 1, . . . , N-1, the output vector will be a permutation of the DFT, i.e., not be in monotonic order. Thus when an FFT is performed, the output or resultant data may have to be reordered for further use. One way to reorder is a Look Up table (LUT), with the index or location in the output vector stored in the LUT, i.e., for the nth element in the DFT, the nth location in the LUT would have the index or location in the FFT output vector where the nth element can be found.
These or similar transforms are often found in, e.g., communication systems employing orthogonal frequency division multiplexing (OFDM). One such system is the 3GPP LTE (3rd Generation Partnership Project) (Long Term Evolution) system. In this system there are 35 or more presently defined FFT sizes. If a LUT is used for all reordering, the LUT would need in excess of 16,500 entries.